#include "game.h"
#include<bits/stdc++.h>
int countt[205][205];
std :: vector<std :: pair<int,int> >v[205];
int vis[205];
bool flag=0;
int noww[205];
int knoww[205];
std :: vector<int> ans,id;
int place[205];
void swapp(int x,int y)
{
    std::swap(ans[x],ans[y]);
    std::swap(place[ans[x]],place[ans[y]]);
}
void dfs(int x,int fa)
{
    vis[x]=1;
    for(int i=0;i<v[x].size();i++)
    {
        int xx=v[x][i].first;
        if(fa==v[x][i].second)
        {
            continue;
        }
        if(vis[xx]==1)
        {
            vis[xx]=2;
            id.push_back(xx);
            vis[x]=2;
            id.push_back(x);
            flag=1;
            return;
        }
        dfs(xx,v[x][i].second);
        if(vis[xx]==2&&vis[x]==2)
        {
            flag=0;
            return;
        }
        if(vis[xx]==2&&flag)
        {
            vis[x]=2;
            id.push_back(x);
            return;
        }
    }
}
void dfss(int x,int fa)
{
    for(int i=0;i<v[x].size();i++)
    {
        int xx=v[x][i].first;
        if(v[x][i].second==xx)
        {
            continue;
        }
        if(vis[xx]==2)
        {
            continue;
        }
        vis[xx]=1;
        swapp(v[x][i].second-1,place[xx]);
        //std::cerr<<"~~~~~~~~~~~~~~~~~~~"<<std::endl;
        //ans[v[x][i].second-1]=xx;
        dfss(xx,v[x][i].second);
    }
}
std :: vector<int> guess(int n, int limit) {
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++)
	{
        v[i].clear();
	}
	ans.resize(n);
	for(int i = 1; i <= n; i ++)
		ans[i - 1] = i;
    int tt=count(ans);
    //std::cerr<<1;
    for(int i=1;i<=n;i++)
    {
        int cnt=0,id1=0,id2=0;
        for(int j=1;j<=n;j++)
        {
            if(i==j)
            {
                continue;
            }
            if(j<i)
            {
                int pp=countt[j][i];
                if(pp>tt)
                {
                    id2=id1;
                    id1=j;
                    cnt++;
                }
                continue;
            }
            std::swap(ans[i-1],ans[j-1]);
            int pp=count(ans);
            countt[i][j]=pp;
            std::swap(ans[i-1],ans[j-1]);
            if(pp>tt)
            {
                id2=id1;
                id1=j;
                cnt++;
            }
        }
        //std::cerr<<"~~~"<<i<<" "<<cnt<<std::endl;
        if(cnt==0)
        {
            vis[i]=114514;
            knoww[i]=i;
            //std::cerr<<i<<std::endl;
        }
        else if(cnt==2)
        {
            v[id1].push_back({id2,i});
            v[id2].push_back({id1,i});
            //std::cerr<<"::"<<id1<<" "<<id2<<" "<<i<<std::endl;
        }
        else
        {
            vis[i]=114514;
            knoww[i]=id1;
            //std::cerr<<i<<" "<<id1<<std::endl;
        }
    }
    for(int i=1;i<=n;i++)
    {
        ans[i-1]=i;
        place[i]=i-1;
    }
    for(int i=1;i<=n;i++)
    {
        if(knoww[i]!=0)
        {
            if(knoww[i]>i)
            {
                swapp(i-1,place[knoww[i]]);
            }
            knoww[i]=0;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==0)
        {
            dfs(i,0);
            for(int j=0;j<id.size();j++)
            {
                dfss(id[j],0);
                for(int k=0;k<v[id[j]].size();k++)
                {
                    if(v[id[j]][k].first==id[(j+1)%id.size()])
                    {
                        noww[j]=v[id[j]][k].second;
                    }
                }
                //std::cerr<<id[j]<<" ";
            }
            //std::cerr<<'\n';

            for(int j=0;j<id.size();j++)
            {
                //ans[noww[j]-1]=id[j];
                swapp(noww[j]-1,place[id[j]]);
            }
            int t1=count(ans);
            for(int j=0;j<id.size();j++)
            {
                //ans[noww[j]-1]=id[(j+1)%id.size()];
                swapp(noww[j]-1,place[id[(j+1)%id.size()]]);
            }
            int t2=count(ans);
            if(t1>t2)
            {
                for(int j=0;j<id.size();j++)
                {
                    swapp(noww[j]-1,place[id[j]]);
                }
            }
            id.clear();
        }
    }
    /*for(int i=0;i<ans.size();i++)
    {
        std::cerr<<ans[i]<<" ";
    }*/
	return ans;
}
